import java.util.LinkedList;
import java.util.List;

public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }

    private static Node createTree(List<Integer> a) {
        int i = 1;
        Node root = new Node(a.get(0));  // 根节点
        Node current;
        Integer value;

        //层序创建二叉树
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (i < a.size()) {
            current = queue.poll();//从链表中移除并获取第一个节点
            value = a.get(i++);
            if (value != null) {
                Node left = new Node(value);
                current.left = left;//创建当前节点的左孩子
                queue.offer(left); // 在链表尾部 左孩子入队
            }
            value = a.get(i++);
            if (value != null) {
                Node right = new Node(value);
                current.right = right;//创建当前节点的右孩子
                queue.offer(right);// 在链表尾部 右孩子入队
            }
        }
        return root;
    }
}
